package main

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
// 
//
//示例 1：
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//示例 2：
//
//输入：n = 1
//输出：["()"]
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/generate-parentheses
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

func generateParenthesis(n int) []string {
	list := []string{}
	type DFSfunc func(left int, right int, str string)
	var dfs DFSfunc
	dfs = func(left int, right int, str string){
		if left==0&&right==0{
			list = append(list, str)
		}

		if left>0{
			dfs(left-1,right,str+"(")
		}


		if right>left{
			dfs(left,right-1,str+")")
		}
	}

	dfs(n,n,"")
	return list


}

